package common.t36.validsudoku;

import java.util.ArrayList;
import java.util.List;


/**
 * https://leetcode-cn.com/problems/valid-sudoku/
 * 判断数独是否是合法的（不是指是否有解）
 * 执行用时：2 ms, 在所有 Java 提交中击败了51.55%的用户
 * 内存消耗：38.5 MB, 在所有 Java 提交中击败了45.23%的用户
 *
 * @Author luxiaoxiao
 * @Date 2022/1/9
 */
public class Solution {

	public static void main(String[] args) {
		Solution solution = new Solution();
		char[][] board = {
			{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
			{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
			{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
			{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
			{'4', '.', '.', '8', '.', '3', '.', '.', '1'},
			{'7', '.', '.', '.', '2', '.', '.', '.', '6'},
			{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
			{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
			{'.', '.', '.', '.', '8', '.', '.', '7', '9'}
		};
		System.out.println(solution.isValidSudoku(board));
	}


	/**
	 * 判断数独是否是合法的
	 * 就是简单的穷举，判断是否合法（不是指是否有解）
	 *
	 * @Author luxiaoxiao
	 * @Date 2022/1/9
	 */
	public boolean isValidSudoku(char[][] board) {
		// 检查行数据是否有重复
		for (char[] chars : board) {
			List<Character> list = new ArrayList<Character>();
			for (char aChar : chars) {
				if (aChar == '.') {
					continue;
				}
				if (list.contains(aChar)) {
					return false;
				}
				list.add(aChar);
			}
		}
		// 检查列数据是否有重复
		for (int j = 0; j < board[0].length; j++) {
			List<Character> list = new ArrayList<Character>();
			for (char[] chars : board) {
				if (chars[j] == '.') {
					continue;
				}
				if (list.contains(chars[j])) {
					return false;
				}
				list.add(chars[j]);
			}
		}
		// 检查块中是否有重复
		ArrayList[] lists = new ArrayList[9];
		for (int i = 0; i < lists.length; i++) {
			lists[i] = new ArrayList<Character>();
		}
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[i].length; j++) {
				if (board[i][j] == '.') {
					continue;
				}
				if (lists[i / 3 * 3 + j / 3].contains(board[i][j])) {
					return false;
				}
				lists[i / 3 * 3 + j / 3].add(board[i][j]);
			}
		}
		return true;
	}
}
